Search Results

Documents authored by Vasilakis, Manolis

Document
DOI: 10.4230/LIPIcs.IPEC.2023.21
Bandwidth Parameterized by Cluster Vertex Deletion Number

Authors: Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1, …, |V(G)|} such that max_{{u, v} ∈ E(G)} | π(u) - π(v) | ≤ b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.
Cite as

Tatsuya Gima, Eun Jung Kim, Noleen Köhler, Nikolaos Melissinos, and Manolis Vasilakis. Bandwidth Parameterized by Cluster Vertex Deletion Number. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.IPEC.2023.21,
  author =	{Gima, Tatsuya and Kim, Eun Jung and K\"{o}hler, Noleen and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Bandwidth Parameterized by Cluster Vertex Deletion Number}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.21},
  URN =		{urn:nbn:de:0030-drops-194401},
  doi =		{10.4230/LIPIcs.IPEC.2023.21},
  annote =	{Keywords: Bandwidth, Clique number, Cluster vertex deletion number, Parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.77
Structural Parameterizations for Two Bounded Degree Problems Revisited

Authors: Michael Lampis and Manolis Vasilakis

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We revisit two well-studied problems, Bounded Degree Vertex Deletion and Defective Coloring, where the input is a graph G and a target degree Δ and we are asked either to edit or partition the graph so that the maximum degree becomes bounded by Δ. Both problems are known to be parameterized intractable for the most well-known structural parameters, such as treewidth. We revisit the parameterization by treewidth, as well as several related parameters and present a more fine-grained picture of the complexity of both problems. In particular: - Both problems admit straightforward DP algorithms with table sizes (Δ+2)^tw and (χ_d(Δ+1))^{tw} respectively, where tw is the input graph’s treewidth and χ_d the number of available colors. We show that, under the SETH, both algorithms are essentially optimal, for any non-trivial fixed values of Δ, χ_d, even if we replace treewidth by pathwidth. Along the way, we obtain an algorithm for Defective Coloring with complexity quasi-linear in the table size, thus settling the complexity of both problems for treewidth and pathwidth. - Given that the standard DP algorithm is optimal for treewidth and pathwidth, we then go on to consider the more restricted parameter tree-depth. Here, previously known lower bounds imply that, under the ETH, Bounded Vertex Degree Deletion and Defective Coloring cannot be solved in time n^o(∜{td}) and n^o(√{td}) respectively, leaving some hope that a qualitatively faster algorithm than the one for treewidth may be possible. We close this gap by showing that neither problem can be solved in time n^o(td), under the ETH, by employing a recursive low tree-depth construction that may be of independent interest. - Finally, we consider a structural parameter that is known to be restrictive enough to render both problems FPT: vertex cover. For both problems the best known algorithm in this setting has a super-exponential dependence of the form vc^𝒪(vc). We show that this is optimal, as an algorithm with dependence of the form vc^o(vc) would violate the ETH. Our proof relies on a new application of the technique of d-detecting families introduced by Bonamy et al. [ToCT 2019]. Our results, although mostly negative in nature, paint a clear picture regarding the complexity of both problems in the landscape of parameterized complexity, since in all cases we provide essentially matching upper and lower bounds.
Cite as

Michael Lampis and Manolis Vasilakis. Structural Parameterizations for Two Bounded Degree Problems Revisited. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 77:1-77:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.ESA.2023.77,
  author =	{Lampis, Michael and Vasilakis, Manolis},
  title =	{{Structural Parameterizations for Two Bounded Degree Problems Revisited}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{77:1--77:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.77},
  URN =		{urn:nbn:de:0030-drops-187302},
  doi =		{10.4230/LIPIcs.ESA.2023.77},
  annote =	{Keywords: ETH, Parameterized Complexity, SETH}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.62
Parameterized Max Min Feedback Vertex Set

Authors: Michael Lampis, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Given a graph G and an integer k, Max Min FVS asks whether there exists a minimal set of vertices of size at least k whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters. Using standard DP techniques, we first present an algorithm of time tw^O(tw) n^O(1), significantly generalizing a recent algorithm of Gaikwad et al. of time vc^O(vc) n^O(1), where tw, vc denote the input graph’s treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a vc^o(vc) n^O(1) algorithm would refute the ETH. With respect to the natural parameter k, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity 10^k n^O(1). We point out that this algorithm is incorrect and present a branching algorithm of complexity 9.34^k n^O(1).
Cite as

Michael Lampis, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Max Min Feedback Vertex Set. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.MFCS.2023.62,
  author =	{Lampis, Michael and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Parameterized Max Min Feedback Vertex Set}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.62},
  URN =		{urn:nbn:de:0030-drops-185965},
  doi =		{10.4230/LIPIcs.MFCS.2023.62},
  annote =	{Keywords: ETH, Feedback vertex set, Parameterized algorithms, Treewidth}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact